package com.example.untils;

import com.example.entity.dto.EageDto;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MyTopologicalSort {

    int N = 105;
    int n, m, idx = 0;
    int[] h = new int[N];
    int[] e = new int[N];
    int[] ne = new int[N];
    int[] q = new int[N];
    int[] d = new int[N];
    private List<Integer> res = new ArrayList<>();

    private void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    private void bfs()
    {
        int hh, tt;
        hh = tt = 0;

        for(int i = 1; i <= n; ++i)
            //1 寻找入度为0的点
            if(d[i] == 0)
                q[tt ++] = i;

        while(hh < tt){
            int t = q[hh ++];
            res.add(t);

            for(int i = h[t]; i != -1; i = ne[i]){
                int k = e[i];

                //2 寻找入度为0的点
                d[k] --;
                if(d[k] == 0) q[tt ++] = k;
            }
        }
    }

    /**
     *
     * @param nx 点的数量
     * @param eageList 谁连谁  下标都从1开始映射。 映射 工序--> 下标
     * @return
     */
    public int haveCycle(int nx, List<EageDto> eageList) {
        Arrays.fill(h, -1);
        n = nx;
        for(EageDto t : eageList) {
            add(t.getX(), t.getY());
            d[t.getY()]++;  // 记录入度
        }
        bfs();
        for(int i = 1; i <= n; i++) {
            if(d[i] != 0) return -1;
        }
        for(Integer t : res) System.out.print(t + " ");
        System.out.println();
        return 0;
    }

}
